package 单调栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
// 496 下一个更大元素1
// 数组模拟hashmap
public class Solution2 {
    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        int[] recode = new int[10001];
        Arrays.fill(recode,-1);
        Deque<Integer> stack = new LinkedList();
        for(int i = 0;i<nums2.length;i++){
            while(!stack.isEmpty()&&stack.peek()<nums2[i]){
                int top = stack.poll();
                recode[top]=nums2[i];
            }
            stack.push(nums2[i]);
        }
        for(int i=0;i<nums1.length;i++){
            res[i]=recode[nums1[i]];
        }
        return res;
    }
    //hashmap记录
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new LinkedList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[nums1.length];
        for(int i = 0;i<nums2.length;i++){
            while(!stack.isEmpty()&&stack.peek()<nums2[i]){
                int top = stack.poll();
                map.put(nums2[i],top);
            }
            stack.push(nums2[i]);
        }
        for(int i = 0;i<nums1.length;i++){
            res[i]=map.getOrDefault(nums1[i],-1);
        }
        return res;
    }
}
